import com.sun.prism.shader.Solid_TextureYV12_AlphaTest_Loader;

import java.sql.SQLSyntaxErrorException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class Solution {
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        TreeNode(int val){
            this.val = val;
        }
    }
    //递归
    static void inOrderR(TreeNode node){
        if(node != null){
            inOrder(node.left);
            System.out.println(node.val);
            inOrder(node.right);
        }
    }
    //非递归
    static void inOrder(TreeNode node){
        if(node==null)return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp;
        while(true){
            while(node!=null){
                stack.add(node);
                node = node.left;
            }//将左子树加到栈中
            if(stack.empty())
                break;
            node = stack.pop();
            System.out.println(node.val);//输出最左的那个节点值
            node = node.right;
        }
        return;
    }

    static void level(TreeNode root){
        TreeNode temp;
        if(root==null)return;
        Queue<TreeNode> q = new PriorityQueue<>();
        q.add(root);
        while(!q.isEmpty()){
            temp = q.poll();
            System.out.println(temp.left);
            System.out.println(temp.right);
        }

    }

    public static void main(String args[]){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node7;
        node3.right = node8;
        inOrder(node1);
        System.out.println();
    }

}

